package LeetCodeHot100TopInterview;

public class Q062_RobotPath {

    //问机器人走到最右下有几条不同路径
    //行列动态规划
    public int uniquePaths(int m, int n) {

        int[][] dp = new int[m][n];
        //终点  路径为 1
        dp[m - 1][n - 1] = 1;
        //最后一列处理
        for (int i = m - 2; i > -1 ; i--) {
            dp[i][n - 1] = 1;
        }
        //最后一行处理
        for (int i = n - 2; i > -1 ; i--) {
            dp[m - 1][i] = 1;
        }

        for (int i = m - 2; i > -1 ; i--) {
            for (int j = n - 2; j > -1 ; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }



}
